package string_question.leecode.test43;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/7 8:54
 */
public class Solution1 {

    // 方法一 ： 使用进位最朴素的解法(自己的方法)
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        // 按位相乘
        String[] results = num1.length() <= num2.length() ? helper(num1, num2) : helper(num2, num1);
        // 合并
        return getAns(results, 0, results.length - 1);
    }

    private String[] helper(String num1, String num2) {
        List<String> temp = new ArrayList<>();
        for (int i = num1.length() - 1; i >= 0; i--) {
            int c1 = num1.charAt(i) - '0';
            if (c1 != 0) {
                int carry = 0;
                StringBuilder t = new StringBuilder();
                for (int j = i + 1; j < num1.length(); j++) {
                    t.append("0");
                }
                for (int j = num2.length() - 1; j >= 0; j--) {
                    int c2 = num2.charAt(j) - '0';
                    int c_num = c1 * c2 + carry;
                    t.append(c_num % 10);
                    carry = c_num / 10;
                }
                if (carry != 0) {
                    t.append(carry + "");
                }
                temp.add(t.reverse().toString());
            }
        }
        String[] res = new String[temp.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = temp.get(i);
        }
        return res;
    }

    private String getAns(String[] results, int l, int r) {
        if (l == r) return results[l];
        int mid = (l + r) / 2;
        String l_s = getAns(results, l, mid);
        String r_s = getAns(results, mid + 1, r);
        // 合并两个字符串
        return merger(l_s, r_s);

    }

    private String merger(String l_s, String r_s) {
        StringBuilder ans = new StringBuilder();
        int ln = l_s.length() - 1, rn = r_s.length() - 1;
        int carry = 0;
        while (ln >= 0 || rn >= 0) {
            int c1 = ln >= 0 ? l_s.charAt(ln--) - '0' : 0;
            int c2 = rn >= 0 ? r_s.charAt(rn--) - '0' : 0;
            int sum = c1 + c2 + carry;
            ans.append(sum % 10);
            carry = sum / 10;
        }
        if (carry != 0) {
            ans.append(carry + "");
        }
        return ans.reverse().toString();
    }

    @Test
    public void test() {
        String s = multiply("123", "456");
        System.out.println(s);
    }

    @Test
    public void test2() {
        String[] helper = helper("123456789","987654321");
        System.out.println(helper.length);
        for (String s : helper) {
            System.out.println(s);
        }

        System.out.println("——————————————————————结算结果如下————————————————————————————————");
        String s = getAns(helper, 0, helper.length - 1);
        System.out.println(s);
    }
}
